Search for: All records

Online traffic classification enables critical applications such as network intrusion detection and prevention, providing Quality-of-Service, and real-time IoT analytics. However, with increasing network speeds, it has become extremely challenging to analyze and classify traffic online. In this paper, we present Leo, a system for online traffic classification at multi-terabit line rates. At its core, Leo implements an online machine learning (ML) model for traffic classification, namely the decision tree, in the network switch's data plane. Leo's design is fast (can classify packets at switch's line rate), scalable (can automatically select a resource-efficient design for the class of decision tree models a user wants to support), and runtime programmable (the model can be updated on-the-fly without switch downtime), while achieving high model accuracy. We implement Leo on top of Intel Tofino switches. Our evaluations show that Leo is able to classify traffic at line rate with nominal latency overhead, can scale to model sizes more than twice as large as state-of-the-art data plane ML classification systems, while achieving classification accuracy on-par with an offline traffic classifier. 

In this paper, we introduce new relaxations for the hypograph of composite functions assuming that the outer function is supermodular and concave extendable. Relying on a recently introduced relaxation framework, we devise a separation algorithm for the graph of the outer function over P, where P is a special polytope to capture the structure of each inner function using its finitely many bounded estimators. The separation algorithm takes [Formula: see text] time, where d is the number of inner functions and n is the number of estimators for each inner function. Consequently, we derive large classes of inequalities that tighten prevalent factorable programming relaxations. We also generalize a decomposition result and devise techniques to simultaneously separate hypographs of various supermodular, concave-extendable functions using facet-defining inequalities. Assuming that the outer function is convex in each argument, we characterize the limiting relaxation obtained with infinitely many estimators as the solution of an optimal transport problem. When the outer function is also supermodular, we obtain an explicit integral formula for this relaxation.